Computer systems commonly have a plurality of components, such as processors, memory, and input/output devices, and a shared bus for transferring information among two or more of the components. The components commonly are coupled to the bus in the form of component modules, each of which may contain one or more processors, memory, and/or input/output devices. Information is transmitted on the bus among component modules during bus "cycles," each bus cycle being a period of time during which a module has control of the bus and is permitted to transfer, or drive, a limited quantity of information on the bus.
A shared bus generally consists of sets of electrical paths (e.g., traces on a printed circuit board), each set being specialized for carrying a specific type of information. Each set of electrical paths (or hardware lines) is coupled to selected component modules that provide and/or utilize the information carried on that set of hardware lines. Buses commonly include one set of hardware lines for carrying data, one set for carrying the addresses identifying the data, and another set for carrying control signals allowing component modules to control the bus without conflict. The same set of hardware lines may be used for more than one purpose. For example, data and addresses may be carried sequentially on the same set of hardware lines. Specialized sets of hardware lines within a shared bus may also be referred to as buses. For example, a shared bus may contain a data bus, an address bus, and other buses.
Modules communicate with one another via a shared bus in the form of "transactions" taking one or more cycles to complete, such as "read" and "write" transactions. In a typical read transaction, a module will send information on the bus during one or more cycles identifying data that it needs to read from another module and requesting that the identified data be sent to it. The responding module then processes the request and returns the data.
In many conventional bus systems, the bus cannot be used for any other purpose between initiation of a read transaction and return of the requested data. If the latency time of the memory is several bus cycles, many bus cycles may be "wasted" in that no information is carried on the bus during the latency period. By contrast, in "split transaction" buses, a response need not immediately follow a request. For example, after a module initiates a read transaction, the module relinquishes control of the bus, and the bus can be used for any other purpose while the responding module processes the transaction. When the responding module is ready to return the requested data, it obtains control of the bus and sends the requested data to the requesting module. Thus, split transaction buses eliminate the need to "waste" bus cycles while requests are being processed. However, split transaction buses result in the need to arbitrate twice for every read transaction; once to obtain control of the bus for sending a read request and once to obtain control of the bus for returning the requested data.
Write transactions have smaller latency problems, because data is already in a fast memory that can be read-out at bus speed. In a typical "write" transaction, a module initiates a "write" by sending predetermined information on the bus during one or more cycles, and then immediately sends data to another module during succeeding cycles. Thus, no cycles are typically wasted in a write transaction, and write transactions need not be split. Hence, split transaction buses generally accommodate conventional (i.e., not split) write transactions along with split read transactions to relieve the need to arbitrate a second time.
Typically, only one module can send, or drive, information on a shared bus in a given cycle. Thus, any shared bus system must have a bus "arbitration" scheme for determining which module is entitled to drive information on the bus in a particular cycle. Many conventional bus arbitration schemes are available. In most arbitration schemes, each module in a shared bus system communicates that it wants to drive the bus, and an arbitration algorithm implemented on one or more processors determines which requesting module is entitled to drive the bus during a given cycle. There are two basic approaches to high performance bus arbitration: centralized arbitration and distributed arbitration.
In a centralized arbitration scheme, each module seeking to use the bus sends an arbitration signal to a central arbiter circuit. The central arbiter circuit processes the arbitration signals to determine the module entitled to use the bus during the next available cycle (i.e., the next bus owner). The central arbiter circuit then sends arbitration response signals back to the modules informing each module whether it is entitled to use the bus. The module that has "won" the arbitration then drives information on the bus. Because multiple communications are necessary during each arbitration, centralized arbitration typically has a undesirably long latency period between the time arbitration signals are sent and the time when the arbitration winner drives the bus.
In a distributed arbitration scheme, each module sends its arbitration signals to each other module in the system. Each module contains a logical circuit for executing an arbitration algorithm to determine the next bus owner based on these arbitration signals. Upon receiving the arbitration signals, each module determines the next bus owner. The module that has won the arbitration then drives its information on the bus. Distributed arbitration commonly has a shorter latency period than centralized arbitration, because only one communication is necessary during each arbitration. Distributed arbitration, however, is generally more costly than centralized arbitration because it requires separate logical circuits to execute an arbitration algorithm within each module, and also requires extra hardware lines for communicating arbitration signals from each module to each other module.
In addition to the above limitations, in most conventional and distributed arbitration schemes, bus cycles are often wasted in between transactions due to various inefficiencies in the schemes. For example, if a bus owner sends a transaction to a module that is too busy to handle it, the transaction will be aborted, wasting a cycle. Also, in arbitration schemes having a latency period between arbitration and control of the bus, cycles are often wasted during the latency period of an arbitration in circumstances where no module is permitted to drive the bus. Each of these problems results in reduced bandwidth.
A number of approaches have been used to improve or alter the performance characteristics of a bus. In some centralized and distributed arbitration buses, for example, the frequency at which data is sent on the bus can be increased by conventional pipelining, that is by having one or more stages of an arbitration for bus ownership during a future cycle occur during a cycle in which the current bus owner is driving data on the bus. Less bus time, therefore, is likely to be spent solely on arbitration and data can be sent over the bus at a higher rate. While this improves the rate of data transmission over the bus, it does not eliminate the above-discussed hardware efficiency problems of distributed buses or latency limitations of centralized buses. In other types of buses, arbitration signals are processed in the same cycle that they are sent, so that arbitration determines bus ownership for the immediately succeeding bus cycle. This approach minimizes the number of cycles between arbitration and bus control by the arbitration winner, but increases the minimum time period necessary during each cycle, thereby reducing the maximum bus frequency. A high frequency is generally desirable in that it generally allows for a higher bandwidth.
Accordingly, there is a need for a shared bus arbitration scheme having improvements over existing buses in terms of hardware efficiency, latency, maximum frequency and/or bandwidth.